package gold.digger;

import gold.utils.InputUtil;

import java.util.*;
import java.util.Arrays;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC417 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {

        int m = 0, n = 0;

        public int[][] directions = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        public List<List<Integer>> pacificAtlantic(int[][] heights) {
            m = heights.length;
            n = heights[0].length;
            Set<Integer> sourcePacific = new HashSet<>(), sourceAtlantic = new HashSet<>();
            for (int i = 0; i < n; i++) sourcePacific.add(i);
            for (int i = 0; i < m; i++) sourcePacific.add(i * n);
            for (int i = 0; i < n; i++) sourceAtlantic.add((m - 1) * n + i);
            for (int i = 0; i < m; i++) sourceAtlantic.add((i + 1) * n - 1);
            BFS(heights, sourcePacific);
            BFS(heights, sourceAtlantic);
            List<List<Integer>> ans = new ArrayList<>();
            sourceAtlantic.retainAll(sourcePacific);
            for (Integer pos : sourceAtlantic) {
                ans.add(new ArrayList<>(Arrays.asList(pos / n, pos % n)));
            }

            return ans;
        }

        public void BFS(int[][] heights, Set<Integer> source) {
            Deque<Integer> queue = new LinkedList<>(source);
            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    int cur = queue.pollFirst(), curX = cur / n, curY = cur % n;
                    for (int[] direction : directions) {
                        int nextX = curX + direction[0], nextY = curY + direction[1], next = nextX * n + nextY;
                        if (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n && !source.contains(next) && heights[nextX][nextY] >= heights[curX][curY]) {
                            source.add(next);
                            queue.offerLast(next);
                        }
                    }
                }
            }
        }
    }


    /*
     * @param 此题目参考了别人代码
     * 这是因为问题情况较为复杂
     * 可以借鉴思想，多多学习
     * @return:
     */
    class Solution_Old {
        private int row, col;
        private int[][] directions = {
                {0, 1},
                {0, -1},
                {1, 0},
                {-1, 0},
        };

        private boolean inArea(int x, int y) {
            return x >= 0 && x < row && y >= 0 && y < col;
        }

        private void dfs(int x, int y, int[][] matrix, int[][] travelled) {
            travelled[x][y] = 1;
            for (int[] d : directions) {
                int newx = x + d[0];
                int newy = y + d[1];
                if (!inArea(newx, newy) || matrix[x][y] > matrix[newx][newy] || travelled[newx][newy] == 1)
                    continue;
                dfs(newx, newy, matrix, travelled);
            }
        }

        public List<List<Integer>> pacificAtlantic(int[][] matrix) {
            List<List<Integer>> res = new ArrayList<>();
            if (matrix == null || matrix.length == 0) return res;

            row = matrix.length;
            col = matrix[0].length;

            int[][] pcf = new int[row][col];
            int[][] atl = new int[row][col];

            for (int i = 0; i < row; i++) {
                dfs(i, 0, matrix, pcf);
                dfs(i, col - 1, matrix, atl);
            }

            for (int i = 0; i < col; i++) {
                dfs(0, i, matrix, pcf);
                dfs(row - 1, i, matrix, atl);
            }

            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    if (pcf[i][j] == 1 && atl[i][j] == 1)
                        res.add(Arrays.asList(i, j));
                }
            }

            return res;
        }
    }


    public void run() {
        System.out.println(new Solution().pacificAtlantic(InputUtil.toDoubleIntegerArray("[[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]")));
        System.out.println(new Solution().pacificAtlantic(InputUtil.toDoubleIntegerArray("[[2,1],[1,2]]")));
    }

    public static void main(String[] args) throws Exception {
        LC417 an = new LC417();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
